모든 쌍 최단 경로 문제

플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결하는 대표적인 동적 계획법 기반의 알고리즘이다. 이 알고리즘은 가중치가 있는 방향 그래프 또는 무방향 그래프에서 모든 정점 쌍 사이의 최단 경로 거리를 계산한다. 알고리즘의 핵심 아이디어는 중간에 거쳐갈 수 있는 정점의 범위를 점진적으로 확장시키는 것이다. 즉, 1번부터 k번까지의 정점만을 중간 정점으로 사용할 때의 최단 거리를 반복적으로 갱신하여, 최종적으로 모든 정점을 중간 정점으로 사용할 수 있을 때의 최단 거리 행렬을 완성한다.

알고리즘은 정점의 개수를 V라고 할 때, V x V 크기의 거리 행렬 D를 초기화하여 시작한다. 이 행렬의 각 원소 D[i][j]는 정점 i에서 정점 j로 가는 직접적인 간선의 가중치로 초기화되며, 간선이 없으면 무한대(∞)로, i와 j가 같으면 0으로 설정된다. 이후 k를 1부터 V까지 순회하며, 모든 정점 쌍 (i, j)에 대해 D[i][j]를 min(D[i][j], D[i][k] + D[k][j]) 공식으로 갱신한다. 이는 "i에서 j로 가는 기존 경로"와 "i에서 k를 거쳐 j로 가는 새로운 경로" 중 더 짧은 것을 선택하는 과정이다.

플로이드-워셜 알고리즘은 구현이 간단하고 코드가 짧은 것이 특징이다. 또한 음수 가중치를 갖는 간선이 존재해도 올바르게 동작한다는 장점이 있다. 그러나 알고리즘은 삼중 반복문을 사용하기 때문에 시간 복잡도가 O(V^3)으로, 정점의 수가 많아지면 계산 시간이 급격히 증가한다. 따라서 이 알고리즘은 정점의 수가 수백 개 이내인 상대적으로 작은 규모의 그래프에 적합하다.

이 알고리즘은 최단 거리뿐만 아니라 경로 자체를 복원할 수 있도록 확장 가능하다. 각 정점 쌍 (i, j)에 대해, j에 도달하기 직전의 정점(선행자) 정보를 저장하는 또 다른 행렬을 함께 유지하며 갱신하면, 계산이 끝난 후 역추적을 통해 실제 최단 경로를 구성할 수 있다. 플로이드-워셜 알고리즘은 그래프 이론의 기본 알고리즘으로, 네트워크 라우팅이나 도로 교통망 분석 등 다양한 분야의 기초가 된다.

존슨 알고리즘은 모든 쌍 최단 경로 문제를 해결하는 알고리즘 중 하나이다. 이 알고리즘은 그래프의 가중치에 음수가 존재할 수 있는 경우에도 적용 가능하며, 다익스트라 알고리즘과 벨만-포드 알고리즘을 조합하여 효율적으로 동작한다. 기본 아이디어는 그래프에 새로운 정점을 추가하고 벨만-포드 알고리즘을 사용해 모든 기존 정점까지의 잠재 함수를 계산한 후, 이를 이용해 가중치를 재조정하여 음의 가중치를 제거하는 것이다. 이후 재조정된 그래프에서 각 정점을 출발점으로 다익스트라 알고리즘을 반복 적용하여 최단 경로를 구한다.

알고리즘의 구체적인 단계는 다음과 같다. 먼저, 원래 그래프에 새로운 출발 정점을 추가하고, 이 정점에서 원래 그래프의 모든 정점으로 가중치가 0인 간선을 연결한다. 다음으로, 벨만-포드 알고리즘을 이 새로운 그래프에 대해 한 번 수행하여 새로운 정점으로부터 각 정점까지의 최단 거리, 즉 잠재 함수 h(v)를 계산한다. 만약 이 과정에서 음수 가중치 사이클이 발견되면 알고리즘은 종료된다. 이후, 원래 그래프의 각 간선 (u, v)의 가중치 w(u, v)를 새로운 가중치 ŵ(u, v) = w(u, v) + h(u) - h(v)로 재조정한다. 이 재조정된 가중치는 음수가 아니게 된다.

마지막으로, 재조정된 가중치를 가진 그래프에 대해, 각 정점을 출발점으로 다익스트라 알고리즘을 |V|번 실행한다. 다익스트라 알고리즘으로 구한 정점 u에서 v까지의 거리 d'(u, v)를 원래 그래프의 실제 거리 d(u, v)로 변환하기 위해서는 d(u, v) = d'(u, v) - h(u) + h(v) 계산을 수행한다. 이 알고리즘의 전체 시간 복잡도는 희소 그래프에서 플로이드-워셜 알고리즘보다 우수한 성능을 보인다.

다익스트라 알고리즘의 반복 적용은 모든 쌍 최단 경로 문제를 해결하는 한 가지 방법이다. 이 접근법은 각 정점을 출발점으로 설정하고, 해당 출발점에 대해 단일 출발점 최단 경로 문제를 해결하는 다익스트라 알고리즘을 모든 정점에 대해 한 번씩 실행하는 방식이다. 결과적으로 각 정점에서 다른 모든 정점으로의 최단 거리를 계산하게 된다.

이 방법은 그래프의 모든 간선의 가중치가 음수가 아닐 때 정확한 결과를 보장한다. 다익스트라 알고리즘 자체가 음수 가중치를 허용하지 않기 때문이다. 구현 시 우선순위 큐를 사용하면 각 다익스트라 알고리즘 실행의 시간 복잡도를 개선할 수 있다. 모든 정점 V개에 대해 알고리즘을 실행하므로, 전체 시간 복잡도는 인접 리스트 표현과 이진 힙 기반 우선순위 큐를 사용할 경우 O(V^2 log V + VE) 수준이 된다.

그러나 이 방법은 플로이드-워셜 알고리즘이나 존슨 알고리즘과 비교했을 때 명확한 제약이 존재한다. 가장 큰 제약은 음수 가중치 간선이 있는 그래프에는 적용할 수 없다는 점이다. 또한, 그래프가 희소 그래프인 경우에는 효율적일 수 있지만, 밀집 그래프인 경우에는 다른 알고리즘에 비해 성능상 유리하지 않을 수 있다. 따라서 그래프의 특성(간선 가중치의 부호, 밀도 등)에 따라 적절한 알고리즘을 선택하는 것이 중요하다.

단일 출발점 최단 경로 문제는 모든 쌍 최단 경로 문제와 밀접하게 연관된 그래프 이론의 기본 문제 중 하나이다. 이 문제는 가중치가 있는 방향 그래프 또는 무방향 그래프에서 하나의 특정 정점(출발점)으로부터 그래프 내의 다른 모든 정점까지의 최단 경로와 그 거리를 찾는 것을 목표로 한다. 모든 쌍 최단 경로 문제가 모든 정점 쌍에 대한 해를 구하는 반면, 단일 출발점 문제는 하나의 출발점에 초점을 맞춘다는 점에서 차이가 있다.

이 문제를 해결하는 대표적인 알고리즘으로는 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라 알고리즘은 음수가 아닌 가중치를 가진 그래프에서 효율적으로 동작하며, 우선순위 큐를 사용하여 구현할 경우 시간 복잡도가 낮다. 반면, 벨만-포드 알고리즘은 그래프에 음수 가중치 간선이 존재할 경우에도 사용할 수 있으며, 음수 가중치 사이클의 존재 여부를 감지할 수 있는 특징이 있다.

단일 출발점 최단 경로 문제의 해법은 모든 쌍 최단 경로 문제를 해결하는 데 직접 활용되기도 한다. 예를 들어, 존슨 알고리즘은 모든 정점에 대해 다익스트라 알고리즘을 반복 적용하는 방식을 취한다. 먼저 벨만-포드 알고리즘을 사용하여 그래프의 가중치를 재조정한 후, 재조정된 그래프에서 각 정점을 출발점으로 하는 다익스트라 알고리즘을 실행함으로써 최종 결과를 얻는다. 이는 단일 출발점 알고리즘이 모든 쌍 문제의 구성 요소로 사용되는 대표적인 사례이다.

이러한 문제들은 운송 네트워크 분석, 라우팅 프로토콜 설계, 게임 인공지능의 경로 탐색 등 다양한 컴퓨터 과학 및 공학 분야에서 광범위하게 응용된다.

음수 가중치 사이클은 가중치가 있는 방향 그래프에서, 사이클을 구성하는 모든 간선의 가중치 합이 음수가 되는 사이클을 의미한다. 이는 모든 쌍 최단 경로 문제를 해결하는 데 있어 중요한 제약 조건이 된다. 음수 가중치 사이클이 존재하면, 해당 사이클을 무한히 순회함으로써 경로의 비용을 계속해서 줄일 수 있기 때문에, 최단 경로가 정의되지 않거나 음의 무한대로 발산하게 된다. 따라서 플로이드-워셜 알고리즘이나 존슨 알고리즘과 같은 모든 쌍 최단 경로 알고리즘은 일반적으로 입력 그래프에 음수 가중치 사이클이 없어야 정상적으로 동작한다.

음수 가중치 사이클을 탐지하는 것은 알고리즘 수행 과정에서 중요한 부분이다. 예를 들어, 플로이드-워셜 알고리즘은 실행이 완료된 후, 대각선 원소(자기 자신으로의 거리)를 검사하여 음수 값이 존재하는지 확인함으로써 음수 가중치 사이클의 존재를 감지할 수 있다. 존슨 알고리즘은 먼저 벨만-포드 알고리즘을 사용하여 그래프에 음수 가중치 사이클이 존재하는지 검사하는 전처리 단계를 포함한다. 만약 사이클이 발견되면 알고리즘은 중단된다.

이러한 사이클은 실제 응용 분야에서 특정 상황을 모델링할 수 있다. 예를 들어, 금융 네트워크에서 통화 환전 거래를 모델링할 때, 음수 가중치 사이클은 차익 거래 기회를 나타낼 수 있다. 즉, 일련의 통화 교환을 통해 처음 투자한 금액보다 더 많은 금액을 얻을 수 있는 순환 경로를 의미한다. 그러나 대부분의 물류 경로 최적화나 네트워크 라우팅 문제에서는 음수 가중치 사이클이 발생하지 않는 것을 전제로 한다.